#include <iostream>
#include <fstream>
namespace testSpace
{
	template <typename T>
	class myStack
	{
	private:
		int size;
		int capacity;
		T *data;
		void morecapacity();

	public:
		myStack(int a) : size(0), capacity(a), data(new T[this->capacity]) {}
		void myPush(T a);
		void myPop();
		auto myTop() const;
		bool isEmpty();
		int getSize() const;
		~myStack();
	};
	typedef struct point
	{
		int x;
		int y;
	} points;

	template <typename T>
	void myStack<T>::morecapacity()
	{
		int newcapacity = capacity * 2;
		T *newData = new T[newcapacity];
		for (int i = 0; i < size; i++)
		{
			newData[i] = data[i];
		}
		delete[] data;
		data = newData;
		capacity = newcapacity;
	}
	template <typename T>
	myStack<T>::~myStack()
	{
		delete[] data;
	}
	template <typename T>
	void myStack<T>::myPush(T a)
	{
		if (size == capacity)
			morecapacity();
		data[size] = a;
		size++;
	}
	template <typename T>
	void myStack<T>::myPop()
	{
		if (size == 0)
		{
			std::cout << "空栈！" << std::endl;
			return;
		}
		size -= 1;
		return;
	}
	template <typename T>
	auto myStack<T>::myTop() const
	{
		if (size == 0)
		{
			std::cout << "空栈！" << std::endl;
			return data[size];
		}
		return data[size - 1];
	}
	template <typename T>
	int myStack<T>::getSize() const
	{
		return size;
	}
	template <typename T>
	bool myStack<T>::isEmpty()
	{
		if (size == 0)
			return true;
		return false;
	}

	void foundMaze(char maze[10][10], int &starx, int &stary, int &endx, int &endy)
	{
		std::ofstream ofs;
		ofs.open("mytest.txt", std::ios::out);
		if (!ofs)
		{
			std::cout << "无法打开文件" << std::endl;
			return;
		}

		for (int i = 0; i < 10; i++)
		{
			maze[i][0] = '#';
			maze[i][9] = '#';
			maze[0][i] = '#';
			maze[9][i] = '#';
		}

		std::cout << "请输入起点行和列 (x,y大于0，小于9): ";
		std::cin >> starx >> stary;
		maze[starx][stary] = 'S';
		std::cout << "请输入终点行和列(x,y大于0，小于9) : ";
		std::cin >> endx >> endy;
		maze[endx][endy] = 'E';
		std::cout << "请创建迷宫，*为通道，#为墙体" << std::endl;
		for (int i = 1; i < 9; i++)
			for (int j = 1; j < 9; j++)
			{
				std::cin >> maze[i][j];
			}

		for (int i = 0; i < 10; i++)
		{
			for (int j = 0; j < 10; j++)
			{
				ofs << maze[i][j];
				if (j != 9)
				{
					ofs << " ";
				}
			}
			ofs << '\n';
		}
		ofs.close();
	}
	bool judege(myStack<points> &judegestack, int endxx, int endyy)
	{
		if (judegestack.myTop().x == endxx && judegestack.myTop().y == endyy)
		{
			while (judegestack.isEmpty())
			{
				std::cout << judegestack.myTop().x;
				std::cout << "    " << judegestack.myTop().y << std::endl;
			}
			return true;
		}
		return false;
	}
	points &creat(int xx, int yy)
	{
		points tmp;
		tmp.x = xx;
		tmp.y = yy;
		return tmp;
	}
	bool ispast(myStack<points> &mystack, char maze[10][10], int xxx, int yyy)
	{
		if (maze[mystack.myTop().x][mystack.myTop().y] == '*')
		{
			xxx = mystack.myTop().x;
			yyy = mystack.myTop().y;
			return true;
		}
		return false;
	}
	bool searchMaze(myStack<points> &mystack, int endx, int endy, char maze[10][10])
	{
		while (!mystack.isEmpty())
		{
			if (judege(mystack, endx, endy))
				return true;
			points tmp = creat(mystack.myTop().x, mystack.myTop().y + 1); // 1
			mystack.myPush(tmp);
			int tmp1 = 0;
			int tmp2 = 0;
			if (ispast(mystack, maze, tmp1, tmp2))
			{
				maze[tmp1][tmp2] = '#';
				continue;
			}
			else
			{
				mystack.myPop();
			}

			if (judege(mystack, endx, endy))
				return true;
			points tmpt = creat(mystack.myTop().x + 1, mystack.myTop().y); // 2
			mystack.myPush(tmpt);
			int tmpt1 = 0;
			int tmpt2 = 0;
			if (ispast(mystack, maze, tmpt1, tmpt2))
			{
				maze[tmpt1][tmpt2] = '#';
				continue;
			}
			else
			{
				mystack.myPop();
			}

			if (judege(mystack, endx, endy))
				return true;
			points tmph = creat(mystack.myTop().x - 1, mystack.myTop().y); // 3
			mystack.myPush(tmph);
			int tmph1 = 0;
			int tmph2 = 0;
			if (ispast(mystack, maze, tmph1, tmph2))
			{
				maze[tmph1][tmph2] = '#';
				continue;
			}
			else
			{
				mystack.myPop();
			}

			if (judege(mystack, endx, endy))
				return true;
			points tmpf = creat(mystack.myTop().x, mystack.myTop().y - 1); // 4
			mystack.myPush(tmpf);
			int tmpf1 = 0;
			int tmpf2 = 0;
			if (ispast(mystack, maze, tmpf1, tmpf2))
			{
				maze[tmpf1][tmpf2] = '#';
				continue;
			}
			else
			{
				mystack.myPop();
			}
		}
	}
}

int main()
{
	testSpace::myStack<testSpace::points> mystack(50);
	testSpace::points p = {0, 0};
	int endx = 0;
	int endy = 0;
	char maze[10][10];
	testSpace::foundMaze(maze, p.x, p.y, endx, endy);
	mystack.myPush(p);
	testSpace::searchMaze(mystack, endx, endy, maze);
}